package leetcode_1401_1500;

import java.util.Arrays;

public class LeeCode_1478 {
    public static void main(String[] args) {
        System.out.println(minDistance(new int[]{2, 3, 5, 12, 18}, 2));
        System.out.println(minDistance(new int[]{7,4,6,1}, 1));
        System.out.println(minDistance(new int[]{3,6,14,10}, 4));
    }

    private static int minDistance(int[] houses, int k) {
        Arrays.sort(houses);
        int n =houses.length;
        int[][] dp = new int[n][k + 1];
        int[][] tab = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int l = i, r = j, all = 0;
                while (l < r){
                    all += houses[r] - houses[l];
                    l++;
                    r--;
                }
                tab[i][j] = all;
            }
        }
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], 10000000);
        }
        for (int i = 0; i < n; i++) {
            dp[i][1] = tab[0][i];
        }
        for (int t = 2; t <= k; t++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    dp[i][t] = Math.min(dp[i][t], dp[j][t - 1] + tab[j + 1][i]);
                }
            }
        }
        return dp[n - 1][k];
    }
}